//将搜索二叉树里[low,high]区间外的节点全部删除
//递归法
using namespace std;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
//基本思路，若该节点小于low，左子树全去掉，将右子树接到上一个节点；大于high，右孩子全去掉，将左子树接到上一个节点
//递归过程中，两个合适节点之间有一个不合适节点，则将合适节点连接
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(!root) return nullptr;
    
    //修剪操作
    if(root->val>high){
        TreeNode* left=trimBST(root->left,low,high);
        return left;
    }
    if(root->val<low){
        TreeNode* right=trimBST(root->right,low,high);
        return right;
    }
    //若在两个合适节点中间有不合适的，则将递归直到遇到下一个合适的节点然后接为合适节点的左或右孩子

    root->left=trimBST(root->left,low,high);
    root->right=trimBST(root->right,low,high);
    
    return root;
}

//迭代法
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(!root) return nullptr;
    //移动过root直到找到合适根节点
    while(root&&(root->val>high||root->val<low)){
        if(root->val<low) root=root->right;
        else root=root->left;
    }

    TreeNode* cur=root;
    //左子树元素小了
    //左子树最大元素不超过root，只需修剪小于low的节点
    while(cur){
        while(cur->left&&cur->left->val<low)
            cur->left=cur->left->right; //这一步移动没有改变cur的位置
        cur=cur->left;  //移动继续
    }
    //右子树元素大了
    //右子树最小元素不低于root，只需修剪大于high的节点
    cur=root;
    while(cur){
        while(cur->right&&cur->right->val>high)
            cur->right=cur->right->left;
        cur=cur->right;
    }

    return root;
}